﻿#include "Graph.h"

GraphNode::GraphNode(int value)
{
	this->value = value;
	in = 0;
	out = 0;
}

GraphEdge::GraphEdge(GraphNode* from, GraphNode* to, int weight)
{
	this->from = from;
	this->to = to;
	this->weight = weight;
}

Graph::Graph()
{

}

Graph::~Graph()
{
	for (auto iterator1 = nodes.begin(); iterator1 != nodes.end(); ++iterator1)
	{
		delete(iterator1->second);
	}

	nodes.clear();

	for (auto iterator2 = edges.begin(); iterator2 != edges.end(); ++iterator2)
	{
		delete(*iterator2);
	}

	edges.clear();
}

Graph* Graph::generate(int** matrix, int rowCount, int colCount, bool isDigraph)
{
	//for (int y = 0; y < rowCount; y++)
	//{
	//	for (int x = 0; x < colCount; x++)
	//	{
	//		printf("matrix[%d, %d] = %d\n", x, y, *(*(matrix) + x + y * colCount));
	//	}
	//}

	Graph* graph = new Graph();
	
	for (int y = 0; y < rowCount; y++)
	{
		int fromValue = *(*(matrix)+y * colCount);
		int toValue = *(*(matrix)+1 + y * colCount);
		int weight = *(*(matrix)+2 + y * colCount);
		
		GraphNode* fromNode;
		GraphNode* toNode;
		
		auto fromNodeIterator = graph->nodes.find(fromValue);
		if (fromNodeIterator == graph->nodes.end())
		{
			fromNode = new GraphNode(fromValue);
			graph->nodes.insert({ fromValue, fromNode });
		}
		else
		{
			fromNode = fromNodeIterator->second;
		}

		auto toNodeIterator = graph->nodes.find(toValue);
		if (toNodeIterator == graph->nodes.end())
		{
			toNode = new GraphNode(toValue);
			graph->nodes.insert({ toValue, toNode });
		}
		else
		{
			toNode = toNodeIterator->second;
		}

		fromNode->nextNodes.push_back(toNode);
		fromNode->out++;
		toNode->in++;

		GraphEdge* edge = new GraphEdge(fromNode, toNode, weight);
		fromNode->edges.push_back(edge);
		graph->nodes.insert({ fromValue, fromNode });
		graph->nodes.insert({ toValue, toNode });
		graph->edges.insert(edge);

		if (!isDigraph)
		{
			// 无向图，需要再添加一条反向的边
			auto antiFromNode = toNode;
			auto antiToNode = fromNode;
			antiFromNode->nextNodes.push_back(antiToNode);
			antiFromNode->out++;
			antiToNode->in++;
			edge = new GraphEdge(antiFromNode, antiToNode, weight);
			antiFromNode->edges.push_back(edge);
			graph->edges.insert(edge);
		}
	}

	return graph;
}
